package com.acwing.partition14;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/3/8 12:46
 */
public class AC1303斐波那契前n项和 {

    private static final int N = 2000000000;
    //根据题意构造出的A矩阵
    private static long[][] a = new long[][]{{0, 1, 0}, {1, 1, 1}, {0, 0, 1}};
    private static int n, m;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        //f矩阵初始化为 [数列第一项,数列第二项,数列前1项和]
        long[][] res = qmi(a, n - 1), f = new long[][]{{1, 1, 1}};
        f = mul(f, res);
        writer.write(f[0][2] + "\n");
        writer.flush();
    }

    private static long[][] qmi(long[][] a, int k) {
        long[][] res = new long[a.length][a[0].length];
        for (int i = 0; i < res.length; i++) res[i][i] = 1;
        while (k != 0) {
            if ((k & 1) == 1) res = mul(res, a);
            k >>= 1;
            a = mul(a, a);
        }
        return res;
    }

    private static long[][] mul(long[][] a, long[][] b) {
        long[][] res = new long[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[0].length; k++) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j] % m) % m;
                }
            }
        }
        return res;
    }
}
